Graphs are common data structures which widely used for information storage and retrieval. Occasionally some vertices of a graph contain specific features or information, which we value in their effect. We consider modeling this effect formally, and we devise two super- More
Graphs are common data structures which widely used for information storage and retrieval. Occasionally some vertices of a graph contain specific features or information, which we value in their effect. We consider modeling this effect formally, and we devise two super-fast algorithms to approximate the colored average degree. In the first method, we assume the information of each vertex is available; hence, the provided algorithm works with a 2+ϵ approximation factor. Eventually, we waive this assumption and find another algorithm with the same approximation factor, which computes the answer in the sublinear expected time.
Manuscript profile
